\subsection{Statement of theorem}
\begin{definition}
	The simple random walk in \( \mathbb Z^d \) is the Markov chain defined by
	\[
		P(x,x+e_i) = P(x,x-e_i) = \frac{1}{2d}
	\]
	where \( e_i \) is the standard basis.
\end{definition}
\begin{theorem}
	The simple random walk in \( \mathbb Z^d \) is recurrent for \( d = 1, d = 2 \) and transient for \( d \geq 3 \).
\end{theorem}

\subsection{One-dimensional proof}
Consider \( d = 1 \).
In this case, \( P(x,x+1) = P(x,x-1) = \frac{1}{2} \).
We will show that \( \sum_n p_{00}(n) = \infty \), then recurrence will hold.
We have \( p_{00}(n) = \psub{0}{X_n = 0} \).
Note that if \( n \) is odd, \( X_n \) is odd, so \( \psub{0}{X_{2k+1} = 0} = 0 \).
So we will consider only even numbers.
In order to be back at zero after \( 2n \) steps, we must make \( n \) steps `up' away from the origin and make \( n \) steps `down'.
There are \( \binom{2n}{n} \) ways of choosing which steps are `up' steps.
The probability of a specific choice of \( n \) `up' and \( n \) `down' is \( \qty(\frac{1}{2})^{2n} \).
Hence,
\[
	p_{00}(2n) = \binom{2n}{n} \qty(\frac{1}{2})^{2n} = \frac{(2n)!}{(n!)^2} \cdot \frac{1}{2^{2n}}
\]
Recall Stirling's formula:
\[
	n!
	\sim n^n e^{-n} \sqrt{2 \pi n}
\]
Substituting in,
\[
	\frac{(2n)!}{(n!)^2} \cdot \frac{1}{2^{2n}} \sim \frac{1}{\sqrt{\pi n}} = \frac{A}{\sqrt{n}}
\]
for \( A > 0 \); the precise value of \( A \) is unnecessary.
Hence, for some large \( n_0 \), \( \forall n \geq n_0 \), \( p_{00}(2n) \geq \frac{A}{2\sqrt{n}} \).
So
\[
	\sum_n p_{00}(2n) \geq \sum_{n \geq n_0} \frac{A}{2\sqrt{n}} = \infty
\]
Now, let us consider the asymmetric random walk for \( d = 1 \), defined by \( P(x,x+1) = p \) and \( P(x,x-1) = q \).
We can compute \( p_{00}(2n) = \binom{2n}{n} (pq)^n \sim A \frac{(4pq)^n}{\sqrt{n}} \).
If \( p \neq q \), then \( 4pq < 1 \) so by the geometric series we have
\[
	\sum_{n \geq n_0} p_{00}(2n) \leq \sum_{n \geq n_0} 2A (4pq)^n < \infty
\]
So the asymmetric random walk is transient.

\subsection{Two-dimensional proof}
Now, let us consider the simple random walk on \( \mathbb Z^2 \).
For each point \( (x,y) \in \mathbb Z^2 \), we will project this coordinate onto the lines \( y=x \) and \( y=-x \).
In particular, we define
\[
	f(x,y) = \qty(\frac{x+y}{\sqrt{2}}, \frac{x-y}{\sqrt{2}})
\]
If \( X_n \) is the simple random walk on \( \mathbb Z^2 \), we consider \( f(X_n) = (X_n^+, X_n^-) \).
\begin{lemma}
	\( (X_n^+), (X_n^-) \) are independent simple random walks on \( \frac{1}{\sqrt{2}} \mathbb Z \).
\end{lemma}
\begin{proof}
	We can write \( X_n \) as
	\[
		X_n = \sum_{i=1}^n \xi_i
	\]
	where \( \xi_i \) are independent and identically distributed by
	\[
		\prob{\xi_1 = (1,0)} = \prob{\xi_1 = (-1,0)} = \prob{\xi_1 = (0,1)} = \prob{\xi_1 = (0,-1)} = \frac{1}{4}
	\]
	and we write \( \xi_i = (\xi_i^1, \xi_i^2) \).
	We can then see that
	\[
		X_n^+ = \sum_{i=1}^n \frac{\xi_i^1 + \xi_i^2}{\sqrt{2}};\quad X_n^- = \sum_{i=1}^n \frac{\xi_i^1 - \xi_i^2}{\sqrt{2}}
	\]
	We can check that \( (X_n^+), (X_n^-) \) are simple random walks on \( \frac{1}{\sqrt{2}} \mathbb Z \).
	It now suffices to prove the independence property.
	Note that it suffices to show that \( \xi_i^1 + \xi_1^2 \) and \( \xi_i^1 - \xi_i^2 \) are independent, since the \( X_n^+, X_n^- \) are sums of independent and identically distributed copies of these random variables.
	We can simply enumerate all possible values of \( \xi_i^1, \xi_i^2 \) and the result follows.
\end{proof}
We know that \( p_{00}(n) = 0 \) if \( n \) is odd.
We want to find \( p_{00}(2n) = \psub{0}{X_{2n} = 0} \).
Note, \( X_n = 0 \iff X_n^+ = X_n^- = 0 \).
Using the lemma above,
\[
	\psub{0}{X_{2n} = 0} = \psub{0}{X_n^+ = 0, X_n^- = 0} = \psub{0}{X_n^+ = 0} \psub{0}{X_n^- = 0} \sim \frac{A}{\sqrt{n}} \frac{A}{\sqrt{n}} = \frac{A^2}{n}
\]
Hence,
\[
	\sum_{n \geq n_0} \psub{0}{X_{2n} = 0} \geq \sum_{n \geq n_0} = \frac{A^2}{2n} = \infty
\]
which gives recurrence as required.

\subsection{Three-dimensional proof}
Consider \( d = 3 \).
Again, \( p_{00}(n) = 0 \) if \( n \) odd.
In order to return to zero after \( 2n \) steps, we must make \( i \) steps both up and down, \( j \) steps north and south, and \( k \) steps east and west, with \( i+j+k=n \).
There are \( \binom{2n}{i,i,j,j,k,k} \) ways of choosing which steps in each direction we take.
Each combination has probability \( \qty(\frac{1}{6})^{2n} \) of happening.
Hence,
\[
	p_{00}(2n) = \sum_{i,j,k \geq 0, i+j+k=n} \binom{2n}{i,i,j,j,k,k} \qty(\frac{1}{6})^{2n} = \binom{2n}{n} \qty(\frac{1}{2})^{2n} \sum_{i,j,k \geq 0, i+j+k=n} \binom{n}{i,j,k}^2 \qty(\frac{1}{3})^{2n}
\]
The sum on the right hand side is the total probability of the number of ways of placing \( n \) balls in three boxes uniformly at random, so equals one.
Suppose \( n = 3m \).
Then we can show that \( \binom{n}{i,j,k} \leq \binom{n}{m,m,m} \).
\[
	p_{00}(6m) \geq \binom{2n}{n} \qty(\frac{1}{2})^{2n} \binom{n}{m,m,m} \qty(\frac{1}{3})^{n}
\]
Applying Stirling's formula again, we have
\[
	p_{00}(6m) \sim \frac{A}{n^{3/2}}
\]
It is sufficient to consider \( n = 3m \):
\[
	p_{00}(6m) \geq \frac{1}{6^2} p_{00}(6m-2);\quad p_{00}(6m) \geq \frac{1}{6^4} p_{00}(6m-4)
\]
Hence
\[
	\sum_n p_{00}(n) < \infty
\]
So the Markov chain is transient.
